#include <iostream>
using namespace std;
const int N = 100010;
int head, e[N], ne[N], pre[N], idx, tail;

void init()
{
    head = -1;
    idx = 0;
    tail = -1;
}

void push_back(int x)
{
    e[idx] = x;
    if (tail == -1)
    {
        ne[idx] = -1;
        pre[idx] = -1;
        head = tail = idx;
    }
    else
    {
        ne[idx] = -1;
        pre[idx] = tail;
        ne[tail] = idx;
        tail = idx;
    }
    ++idx;
}

void push_front(int x)
{
    pre[idx] = -1;
    e[idx] = x;
    ne[idx] = head;
    pre[head] = idx;
    head = idx;
    if (tail == -1) tail = idx;
    ++idx;
}

void erase(int k)
{
    int next = ne[k - 1];
    int prex = pre[k - 1];
    ne[prex] = next;
    pre[next] = prex;
}

void insert_front(int k, int x)
{
    e[idx] = x;
    ne[idx] = k - 1;
    int prex = pre[k - 1];
    pre[k - 1] = idx;
    //cout << pre[k-1] << endl;
    ne[prex] = idx;
    pre[idx] = prex;
    idx++;
    //cout << ne[idx] << endl;
}

int main()
{
    init();
    push_back(1);
    push_back(2);
    push_front(3);
    insert_front(2, 4);
    while (head != -1)
    {
        cout << e[head] << ' ';
        head = ne[head];
    }
    /*while(tail!= -1)
    {
        cout << e[tail] << ' ';
        tail = pre[tail];
    }*/

    return 0;
}